1. Field of the Invention
This invention relates to a method and apparatus for processing plural pictures to generate a synthesized picture.
2. Description of the Related Art
In keeping up with improvement in computer performance, a wide variety of processing algorithms have been developed in many technical fields to yield tremendous results. Among these image processing techniques, pattern matching is stirring up notice.
The problem of pattern matching, in case the coordinates of points of point sets are more or less inaccurate, as in feature points afforded by e.g., pleissey corner detection or Kanade Lucas Tomari (so called KLT) corner detection algorithm in two point sets S={S1, . . . , Sn) and Q={Q1, . . . , Qm} in a Euclid d-dimensional space Ed, having different densities. What is to be done in such case is to discriminate inliers, as matched points, from outliers, as non-matched points.
Given a transformation T, accuracy of the matching can be calculated using the Haussdorf distance in percent representation. That is, with the so-called n-k outlier effect removed, by employing this Haussdorf distance, matching accuracy is given as shown in the following equation (1):
xe2x80x83hk({S, Q})=minkSxcex5SminQxcex5Qd(S, Q)xe2x80x83xe2x80x83(1).
In the above equation (1), mink means returning the least kth element, and d(xc2x7,xc2x7) is a distance function. As stated in xe2x80x9cA. Efrat and M. J. Katz, Computing Fair and Bottleneck Matchings in Geometric Graphs, in Proc. 7th Annu. Internat. Sympos. Algorithms Comp., pages 115-125, 1996xe2x80x9d, the defect of this Haussdorf index is that a sole point is eventually matched a plural number of times. In such case, meaningful results cannot be achieved in visual geometric like images having different zoom values.
One of the latest technologies in the pattern matching is disclosed in xe2x80x9cH. Alt and L. Guibas, Resemblance of Geometric Objects, in xe2x80x9cJorg-Rudiger Sack and Jorge Urruitia, editors, Handbook of Computational Geometry, Elsevier Science Publishers B. V. North-Holland, Amsterdam, 1998xe2x80x9d. Irani and Raghavan have proposed in xe2x80x9cSandy Irani and Prabhakar Raghavan, Combinatorial and Experimental Results for Randomized Point Matching Algorithms, in Proc. 12th annual ACM Symposium on Computational Geometry, pages 68-77, 1996xe2x80x9d, a randomized Monte Carlo method as a technique for finding the transformation under the supposition that the sets S and Q are matched at least densely, that is that at least portions of points are matched. This randomized Monte Carlo method is based on involute feature points defining the transformation and represents global processing.
The local processing, employed extremely widely in pattern matching, assumes the space of parameters defining a space of a transformation matrix T and applies to these generating parameters the branch and bound method as shown in xe2x80x9cMichiel Hagedoorn and Remco C. Veltkamp, Reliable and Efficient Pattern Matching Using and Affine Invariant Metric, Technical Report UU-CS-1997-33, Utrecht University, Department of Computing Science, October, 1997xe2x80x9d or in xe2x80x9cD. Mount, N. Netanyahu and J. Le Moigne, Improved Algorithms for Robust Point Pattern Matching and Applications to Image Registration, in 14th Annual ACM Symposium on Computational Geometry, 1998xe2x80x9d. For example, if translation and/or rotation of a plane is allowed, a 3xc3x973 matrix generated by three parameters (x, y, xcex8), representing the amount and direction of translation, expressed as T=R2xc3x97[0, 2xcfx80] using the homogeneous coordinates, is defined.
As another technique for finding the pattern matching, there is a majority decision method, which represents an example of generalization of the Hough transformation, as disclosed in xe2x80x9cT. Akutsu, H. Tamaki and T. Tokuyama, Distribution of Distances and Triangles in a Point Set and Algorithms for Computing the Largest Common Point Set, Discrete and Computational Geometry, pages 207-331, 1998xe2x80x9d. Recently, Indyk et al., has proposed in xe2x80x9cP. Indyk, R. Motwani and S. Venkatasubramanian, Geometric Matching under Noise: Combinatorial Bounds and Algorithms, In SODA: Symposium of Datastructures and Algorithms 1999 and in xe2x80x9cM. Gavrirov, P. Indyk, R. Motowni and S.Venkatasubramanian, Geometric Pattern Matching: A Performance Study, In. Proc. of the 15th Symp. of Comp. Geo., 1999xe2x80x9d an algorithm for executing pattern matching by taking the diameter of a point set into account if there exists a noise. Also, Cardoze and Schulman related in xe2x80x9cCardoze and Schulman, Pattern Matching for Spatial Point Sets, In FOCS: IEEE Symposium on Foundations of Computer Science (FOCS), 1998xe2x80x9d the pattern matching with the number theory and proposed a fast algorithm of executing Fourier transform in accordance with the diameter of a point set.
In the field of the above-described picture processing, it is desired to further raise the efficiency of the technique for a user to generate a synthesized picture. Among the techniques for the user to generate synthesized pictures, there are such a system of synthesizing a picture taking into account a digital still camera having lens distortion or an offset optical system in a camera such as a sequence of pictures making up a motion picture.
However, difficulties are encountered in applying a geometrical model for picture synthesis, such that the processing volume becomes enormous while the processing becomes extremely time-consuming. Consequently, a demand is raised for establishing a technique for efficiently synthesizing a picture using a geometrical model.
It is therefore an object of the present invention to provide a picture processing method and apparatus whereby plural pictures can be synthesized efficiently by applying a geometrical model.
In one aspect, the present invention provides an image processing method including a feature extracting step of extracting feature points of two or more images, a matching step of comparing feature points of one of the two or more images to those of other images for effecting matching and a computing step of performing computations for changing the relative position between the one image and the other image based on the results of the matching step.
In this image processing method, feature points of each of two or more images are extracted, the feature points of one of the two or more images are compared to those of the other image or images to effect matching. Based on the results of this matching, computations are carried out to change the relative positions of the one image and the other image or images to synthesize the two or more images.
In another aspect, the present invention provides an image processing apparatus including feature extracting means for extracting feature points of two or more images, matching means for comparing feature points of one of the two or more images to those of other images for effecting matching and computing means for performing computations for changing the relative position between the one image and the other image based on the results of matching by the matching means.
In this image processing apparatus, feature points of each of the two or more images are extracted by the feature extracting means and the feature points of one of the images are compared to those of the other image or images by the matching means by way of matching. Based on the results of this matching, computations are executed by the computing means such as to change the relative position between the one image and the other image or images to synthesize the two or more images.